#define _CRT_SECURE_NO_WARNINGS
#define _ENABLE_ATOMIC_ALIGNMENT_FIX
#include<iostream>
#include<vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <unordered_map>
#include <fstream>
#include <map>
#include <set>
#include <array>
#include <mutex>

using namespace std;



\\Desktop-7v0603l\d




class Solution {
public:
	/**
	 * lru design
	 * @param operators int整型vector<vector<>> the ops
	 * @param k int整型 the k
	 * @return int整型vector
	 */
	unordered_map<int, pair<int, int>> cachdict;
	list<pair<int, int>>   priorityList;
	int capacity = 0;


	void set(int key, int value)
	{
		int currCapcity = priorityList.size();

		list < pair<int, int>> currlist;
		if (currCapcity < capacity)
		{
			priorityList.push_front({ key,value });
			cachdict[key] = { key,value };
		}
		else
		{
			//catch 不足了
			currlist.pop_back();
			cachdict.erase(key);
		}


	}

	int get(int key)
	{
		auto itr = cachdict.find(key);

		if (itr != cachdict.end())
		{
			return 1;
		}
		else
		{
			return 0;
		}



	}




	vector<int> LRU(vector<vector<int> >& operators, int k) {
		// write code here




	}
};







int  count(vector<int> vec)
{

	int count = 0;
	for (auto ele : vec)
	{
		if (ele != -1)
		{
			count++;
		}
	}
	return count;

}
void calc(vector<int> &vec, const int M, int j)
{
	if (count(vec) < M)
	{
		return;
	}
	int i = 0;
	int count1 = 0;
	int p = 0;
	for (int i = j; i < vec.size(); i++)
	{

		if (vec[i] == -1)
			continue;
		count1++;
		if (count1 == M)
		{
			p = i + 1;

			vec[i] = -1;
		}
		if (count1 < M && i == vec.size() - 1)
		{
			i = -1;
		}
	}
	calc(vec, M, p);

}




void readFile(const string&& AbsoluteSourcePath, int head, void(*cb)(const  string&))
{
	ifstream file(AbsoluteSourcePath);
	string str;
	if (head)
	{
		getline(file, str);
	}
	while (getline(file, str))
	{
		cb(str);
	}
}

void myfun(string str)
{
	cout << str << endl;

}







vector<int> twoSum(vector<int>& numbers, int target) {
	// write code here
	map<int, int> value_index;
	for (int i = 0; i < numbers.size(); i++)
	{
		int curr = numbers[i];
		auto itr = value_index.find(target - curr);
		if (itr != value_index.end())
		{
			return{ itr->second + 1,i + 1 };
		}
		else
		{
			value_index[i] = curr;
		}


	}
	return {};

}

int maxLength(vector<int>& arr) {
	// write code here
	int n = arr.size();
	int l = 0, r = 0;
	set<int>s;
	int res = 0;
	while (r < n) {
		if (!s.count(arr[r])) {
			s.insert(arr[r]);
			r++;
		}
		else {
			s.erase(arr[l]);
			l++;
		}
		res = res > s.size() ? res : s.size();
	}
	return res;
}



void merge(int A[], int m, int B[], int n) {
	///由后向前遍历数组


	m = m - 1;
	n = n - 1;
	for (int i = m + n - 1; i > 0; i--)
	{
		if (A[m] >= B[n] && m >= 0)
		{
			A[i] = A[m];
			m--;
		}
		if (A[m] < B[n] && n >= 0)
		{
			A[i] = B[n];
			n--;
		}

	}
}


void dfs(string &str, vector<bool> &visit, string &list, vector<string> &vec)
{
	if (list.size() == str.size())
	{
		auto sx = find(vec.begin(), vec.begin(), list);
		if (find(vec.begin(), vec.begin(), list) != vec.end())
		{

			return;
		}
		else {
			vec.push_back(list);
			return;
		}

	}
	for (int i = 0; i < str.size(); i++)
	{
		if (!visit[i])
		{
			visit[i] = true;
			list.push_back(str[i]);
			dfs(str, visit, list, vec);
			list.pop_back();
			visit[i] = false;


		}

	}

}
vector<int> LIS(vector<int>& arr) {
	// write code here
	// 第一步：利用贪心+二分求最长递增子序列长度
	vector<int> res;
	vector<int> maxLen;
	if (arr.size() < 1) return res;
	res.emplace_back(arr[0]);  // 注：emplace_back(val)作用同push_back，效率更高
	maxLen.emplace_back(1);
	for (int i = 1; i < arr.size(); ++i) {
		if (arr[i] > res.back()) {
			res.emplace_back(arr[i]);
			maxLen.emplace_back(res.size());
		}
		else {
			// lower_bound(begin, end, val)包含在<algorithm>中
			// 它的作用是返回有序数组begin..end中第一个大于等于val的元素的迭代器
			int pos = lower_bound(res.begin(), res.end(), arr[i]) - res.begin();
			res[pos] = arr[i];
			maxLen.emplace_back(pos + 1);
		}
	}
	// 第二步：填充最长递增子序列
	for (int i = arr.size() - 1, j = res.size(); j > 0; --i) {
		if (maxLen[i] == j) {
			res[--j] = arr[i];
		}
	}
	return res;
}


int getLongestPalindrome(string A, int n) {

	// 第 i 个字符到第 j 个字符是否是回文串
	vector<vector<bool>> dp(n, vector<bool>(n, 0));
	int maxs = 0;
	// 字符串首尾字母长度差 (d = j-i)
	for (int d = 0; d < n; d++) {
		// 字符串起始位置 i
		for (int i = 0; i < n - d; i++) {
			// 字符串结束位置 j
			int j = i + d;
			// 如果字符串 i 到 j 的首尾相等，再根据字符串 i-1 到 j-1 来确定，即得到递推公式
			if (A[i] == A[j]) {
				if (d == 0 || d == 1) {
					dp[i][j] = true;
				}
				else {
					dp[i][j] = dp[i + 1][j - 1];
				}
				if (dp[i][j]) {
					// 更新最大长度
					maxs = max(maxs, d + 1);

				}
			}
		}
	}
	return maxs;
}



#include<stack>
bool isValid(string s) {
	// write code here
	stack<char> mystack;
	for (int i = 0; i < s.size(); i++)
	{

		if (s[i] == '(')
		{

			mystack.push(')');
		}
		else if (s[i] == '[')
		{

			mystack.push(']');
		}
		else if (s[i] == '{')
		{
			mystack.push('}');
		}

		else
		{
			if (mystack.empty())
			{
				return false;
			}
			char temp = mystack.top();
			if (temp != s[i])
			{
				return false;
			}
			mystack.pop();

		}


	}
	return  !mystack.empty();


}



vector<int>  matrixs(vector<vector<int>> matrix)
{

	vector<int> res;
	if (matrix.size() == 0)
		return res;
	if (matrix[0].size() == 0)
		return res;
	int up = 0;
	int down = matrix.size() - 1;  //注意，这里设置成size()-1是为了下面的matrix[k][right]访问时不失效  
	int left = 0;
	int right = matrix[0].size() - 1;
	while (true)
	{
		if (left > right) return res;
		for (int k = left; k <= right; k++) //向右
		{
			res.push_back(matrix[up][k]);
		}
		up++; ///下一个起点加一下
		if (up > down) return res;
		for (int k = up; k <= down; k++)//向下
		{
			res.push_back(matrix[k][right]);
		}
		right--;
		if (left > right) return res;
		for (int k = right; k >= left; k--)//向左
		{
			res.push_back(matrix[down][k]);
		}
		down++;///下一个起点加一下
		if (up > down) return res;
		for (int k = down; k >= up; k--) ///向上
		{
			res.push_back(matrix[k][left]);

		}
		left++;
	}


}


long long maxWater(vector<int>& arr) {
	// write code here
	int n = arr.size();
	if (n <= 2)
		return 0;
	int i = 0, j = n - 1, left = arr[0], right = arr[n - 1];
	long long sum_val = 0;
	while (i < j)
	{
		if (left < right)
		{
			i++;
			if (arr[i] >= left)
			{
				left = arr[i];
				continue;
			}
			sum_val += (left - arr[i]);
		}
		else
		{
			j--;
			if (arr[j] > right)
			{
				right = arr[j];
				continue;
			}
			sum_val += (right - arr[j]);
		}
	}
	return sum_val;

}


long long maxWater1(vector<int>& arr) {
	// write code here

	if (arr.size() == 2) return 0;
	int l = 1;
	int r = arr.size() - 2;
	int leftIndex = 0, rightIndex = arr.size() - 1;
	while (arr[leftIndex] < arr[leftIndex + 1])
	{
		leftIndex++;
	}
	while (arr[rightIndex - 1] > arr[rightIndex])
	{
		rightIndex--;
	}

	int minLimit = min(arr[leftIndex], arr[rightIndex]);
	long long  sum = 0;
	while (rightIndex - leftIndex > 1)
	{
		sum = sum + max(minLimit - arr[leftIndex], 0);
		leftIndex++;
	}
	return sum;



}





/// node构造器

struct ListNode
{
	ListNode *next;
	int val;
	ListNode(int para) :val(para)
	{
		next = nullptr;
	}
};

ListNode *ListNodeConstructor(vector <int > & vec)
{
	ListNode *dummy = new ListNode(-1);
	ListNode *p = dummy;
	for (int i = 0; i < vec.size(); i++)
	{
		ListNode * curr = new ListNode(vec[i]);
		p->next = curr;
		p = curr;// 或者p=p->next;

	}
	return dummy->next;

}




/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */





ListNode* mergeTwoLists(struct ListNode* head1, struct ListNode* head2) {
	ListNode* dummyHead = new ListNode(0);
	ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;
	while (temp1 != nullptr && temp2 != nullptr) {
		if (temp1->val <= temp2->val) {
			temp->next = temp1;
			temp1 = temp1->next;
		}
		else {
			temp->next = temp2;
			temp2 = temp2->next;
		}
		temp = temp->next;
	}
	if (temp1 != nullptr) {
		temp->next = temp1;
	}
	else if (temp2 != nullptr) {
		temp->next = temp2;
	}
	return dummyHead->next;
}


ListNode* sortInList(ListNode* head) {
	// write code here


	if (!head) return nullptr;
	int length = 0;
	ListNode *countNode = head;
	while (countNode)  //计算链表长度
	{
		length++;
		countNode = countNode->next;
	}
	ListNode *dummy = new ListNode(-1);
	dummy->next = head;


	for (int subLen = 1; subLen < length; subLen <<= 1)

	{
		ListNode *pre = dummy;
		ListNode *curr = head;
		while (curr)  //链未被拆完则继续 按照subLen进行两两合并
		{
			ListNode *head_1 = curr;
			for (int i = 1; i < subLen && curr &&curr->next; i++)
			{
				curr = curr->next;
			}

			ListNode *head_2 = curr->next;
			curr->next = nullptr; //第一次断链
			curr = head_2;

			for (int i = 1; i < subLen && curr&&curr->next; i++)
			{
				curr = curr->next;
			}
			ListNode *mergedNextNode = nullptr;
			if (curr)
			{

				mergedNextNode = curr->next; //保存合并之后要指向的next节点信息
				curr->next = nullptr; //第二次断链 放在括号里面

			}
			//		curr->next = nullptr; //第二次断链


			ListNode *mergedNode = mergeTwoLists(head_1, head_2);
			pre->next = mergedNode;
			while (pre->next)   //获取已合并链的最末节点
			{
				pre = pre->next;
			}
			curr = mergedNextNode;//下次要两两合并的起始节点

		}
	}
	return dummy->next;
}

int minNumberdisappered(vector<int>& nums) {
	int n = nums.size();
	for (int& num : nums) {
		if (num <= 0) {
			num = n + 1;
		}
	}
	for (int i = 0; i < n; ++i) {
		int num = abs(nums[i]);
		if (num <= n) {
			nums[num - 1] = -abs(nums[num - 1]);
		}
	}
	for (int i = 0; i < n; ++i) {
		if (nums[i] > 0) {
			return i + 1;
		}
	}
	return n + 1;
}

#include <stack>
#include <fstream>
using namespace std;


#include<queue>
/*
void backtrack(vector<vector<string>> &solutions, vector<int> &queens, int n, int row, unordered_set<int> &columns, unordered_set<int> &diagonals1, unordered_set<int> &diagonals2) {
	if (row == n) {


	}
	else {
		for (int i = 0; i < n; i++) {
			if (columns.find(i) != columns.end()) {
				continue;
			}
			int diagonal1 = row - i;
			if (diagonals1.find(diagonal1) != diagonals1.end()) {
				continue;
			}
			int diagonal2 = row + i;
			if (diagonals2.find(diagonal2) != diagonals2.end()) {
				continue;
			}
			queens[row] = i;
			columns.insert(i);
			diagonals1.insert(diagonal1);
			diagonals2.insert(diagonal2);
			backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);
			queens[row] = -1;
			columns.erase(i);
			diagonals1.erase(diagonal1);
			diagonals2.erase(diagonal2);
		}
	}
}

*/
vector<vector<string> > topKstrings(vector<string>& strings, int k) {
	vector<vector<string>> ans;
	map<string, int>  map_count;
	unordered_map<string, int> m;
	for (string& str : strings) {
		++m[str];
	}
	if (k == 0 || k > m.size()) return ans;
	auto cmp = [](auto& lh, auto& rh) {
		return lh.second > rh.second || (lh.second == rh.second && lh.first < rh.first);
	};
	priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp)> q(cmp);    ////注意这里的返回值
	for (auto t : m) {   ///遍历所有元素，开始建立k大堆   
		pair<string, int> temp{ t.first, t.second };
		if (static_cast<int>(q.size()) < k)
			q.push(temp);
		else if (!cmp(q.top(), temp)) {      ///
			q.pop();
			q.push(temp);
		}
		cout << q.top().first << endl;   //注意优先队列的top值  ///	
	}
	while (!q.empty()) {
		ans.emplace_back(vector<string>{q.top().first, to_string(q.top().second)});
		q.pop();
	}
	reverse(ans.begin(), ans.end());
	return ans;
}

class smallInt
{
public:
	smallInt(int i = 0) :val(i)
	{
		cout << "constructor" << endl;
	}
	operator int()const
	{
		cout << "operator";
		return val;
	}
	~smallInt()
	{
		cout << "~~~~";
	}
	size_t val;
};

int MoreThanHalfNum_Solution(vector<int> numbers) {
	int n = numbers.size();
	if (n == 0) return 0;

	int num = numbers[0], count = 1;
	for (int i = 1; i < n; i++) {
		if (numbers[i] == num) count++;
		else count--;
		if (count == 0) {
			num = numbers[i];
			count = 1;
		}
	}
	// Verifying
	count = 0;
	for (int i = 0; i < n; i++) {
		if (numbers[i] == num) count++;
	}
	if (count * 2 > n) return num;
	return 0;
}
#include <chrono>
#include <ctime>
// horse ros    dp[i][j] 代表 word1 中前 i 个字符，变换到 word2 中前 j 个字符，最短需要操作的次数

int minDistance(string word1, string word2) {
	vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));

	for (int i = 0; i < dp.size(); i++) {
		dp[i][0] = i;
	}
	for (int j = 0; j < dp[0].size(); j++) {
		dp[0][j] = j;
	}

	for (int i = 1; i < dp.size(); i++) {
		for (int j = 1; j < dp[i].size(); j++) {
			dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
			if (word1[i - 1] == word2[j - 1]) {
				dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
			}
		}
	}
	return dp.back().back();
}

int longestCommonSubsequence(string text1, string text2) {
	vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
	for (int i = 1; i <= text1.size(); i++) {
		for (int j = 1; j <= text2.size(); j++) {
			if (text1[i - 1] == text2[j - 1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}
	return dp[text1.size()][text2.size()];
}





ListNode *reverse(ListNode * head)
{
	ListNode *curr = nullptr;
	ListNode *pre = nullptr;
	while (head)
	{
		curr = head->next;
		head->next = pre;
		pre = head;
		head = curr;

	}
	return pre;
}
void reorderList(ListNode *head) {
	if (!head || !head->next) return;
	ListNode *slow = head;
	ListNode *first = head;
	while (first->next&&first->next)
	{
		slow = slow->next;
		first = first->next;
	}
	ListNode* mid = slow->next;
	slow->next = nullptr; //断链

	ListNode *l2 = reverse(mid);
	ListNode *l1 = head;
	while (l1 &&l2)
	{
		ListNode *temp1 = l1->next;
		ListNode *temp2 = l2->next;

		l1->next = l2;
		l1 = temp1;

		l2->next = l1;
		l2 = temp2;
	}

	// return head;
}


struct TreeNode
{
	TreeNode *left;
	TreeNode *right;
	int  val;
	TreeNode(int a = 0) :val(a), left(nullptr), right(nullptr)
	{
	}


};




int log2N(int n)
{
	int res = -1;
	while (n)
	{
		res++;
		n >>= 1;
	}
	return res;
}

#include <sstream>
/*
class Codec {
public:

	// Encodes a tree to a single string.
	string serialize(TreeNode* root) {
		if (root == NULL)
			return "#_";
		string res = to_string(root->val) + "_";
		res += serialize(root->left);
		res += serialize(root->right);
		return res;
	}

	// Decodes your encoded data to tree.
	TreeNode* deserialize(string data) {
		std::stringstream ss(data);
		std::string item;
		queue<string> q;
		while (std::getline(ss, item, '_'))
			q.push(item);
		return helper(q);
	}
	TreeNode* helper(queue<string>& q)
	{
		if (q.empty()) return nullptr;
		string val = q.front();
		q.pop();
		if (val == "#")
			return NULL;
		TreeNode* head = new TreeNode(stoi(val));
		head->left = helper(q);
		head->right = helper(q);
		return head;
	}
};
*/


class Codec {
public:

	// Encodes a tree to a single string.
	string serialize(TreeNode* root) {
		if (root == nullptr)
			return "#";

		return to_string(root->val) + ' ' + serialize(root->left) + ' ' + serialize(root->right);
	}

	// Decodes your encoded data to tree.
	TreeNode* rebuildTree(stringstream &ss) {
		string tmp;
		std::getline(ss, tmp, ' ');


		if (tmp == "#")
			return nullptr;

		TreeNode* node = new TreeNode(stoi(tmp));
		node->left = rebuildTree(ss);  //这里当根只有一个节点时 默认是有右子树      这里left 和right可以更换位置  对应的 上面也要更换位置
		node->right = rebuildTree(ss);

		return node;
	}

	TreeNode* deserialize(string data) {
		stringstream ss(data);
		return rebuildTree(ss);
	}
};




void getNext(char *p, int *next)
{
	next[0] = -1;
	int i = 0;
	int j = -1;

	while (i < strlen(p))
	{
		if (j == -1 || p[i] == p[j])
		{
			i++;
			j++;
		}
		else
			j = next[j];
	}
}


int KMP(char *t, char *p)
{
	int *next = (int*)malloc(sizeof(int)*strlen(p));
	getNext(p, next);
	int i = 0, j = 0;
	while (i < strlen(t) && j < strlen(p))
	{
		if (j == -1 || t[i] == p[j])
		{
			i++;
			j++;
		}
		else
			j = next[j];     // 即将子串j位置前的最长前缀 和主串的最长后缀对应起来  能这样做的前提是  主串的j位置前与字串的j位置前已经是相同的了

	}
	if (j == strlen(p))   //这里是因为  t[i] == p[j] 相等后右 j++了
	{
		return i - j;
	}
	else
		return -1;

}




string solve(vector<int>& nums) {
	// write code here
	string str;
	if (nums.size() == 0) return str;
	//int temp = nums[0];

	for (int i = 1; i < nums.size(); i++)
	{
		int curr = nums[i];
		/** 这种做法会使得数组的首字母不会被赋值
		for (int j = i - 1; j >= 0; j--)
		{


			if (nums[j] < curr)
			{
				nums[j + 1] = nums[j];
			}
			else
			{
				nums[j + 1] = curr;
				break;
			}
		}

	}*/
		int j = i - 1;
		while (j >= 0 && nums[j] < curr)
		{
			nums[j + 1] = nums[j];
			j--;
		}
		nums[++j] = curr;
	}

	return  "";

}

int sqrt(int x) {
	// write code here
	long i = 1;
	while (i*i*i < x)  //成倍增加 找到第一个平方大于x的整数
	{
		i *= 2;
	}
	while (i*i*i > x)  //递减找到第一个平方小于x的整数
	{
		i = i - 1;
	}
	return (int)i;
}



class rref
{
public:
	rref()
	{
		cout << "1" << endl;
	}

	~rref()
	{
		cout << "2" << endl;

	}


};

rref fun1()
{

	return rref();


}



#include <type_traits>

template<class T>
void rparatest(T && p)
{
	//	auto d = decltype(p);
	bool a = std::is_rvalue_reference<decltype(p) >::value;
	bool b = std::is_lvalue_reference<T >::value;
	bool c = std::is_lvalue_reference<int & >::value;
	bool d = std::is_lvalue_reference<int && >::value;
	bool f = std::is_same<decltype(p), int>::value;
	bool g = std::is_same<decltype(p), int&>::value;
	bool h = std::is_same<decltype(p), int&&>::value;

}

template<typename T1, typename T2, typename T3>
void flip(T1 f, T2 && t1, T3 &&t2) {
	bool a = std::is_rvalue_reference<decltype(t2) >::value;
	bool b = std::is_lvalue_reference<decltype(t2) >::value;
	//	f(t1, t2);
	f(std::forward<T2>(t1), std::forward<T3>(t2));

}

void g(int & i, int  &&j)
{

}

#include <memory>



#include <functional>

void test2()
{}

string solves(vector<int>& nums) {
	// write code here
	string str;
	if (nums.size() == 0) return str;
	//int temp = nums[0];

	for (int i = 1; i < nums.size(); i++)
	{
		int curr = nums[i];
		/** 这种做法会使得数组的首字母不会被赋值
		for (int j = i - 1; j >= 0; j--)
		{


			if (nums[j] < curr)
			{
				nums[j + 1] = nums[j];
			}
			else
			{
				nums[j + 1] = curr;
				break;
			}
		}

	}*/
		int j = i - 1;
		while (j >= 0 && nums[j] < curr)
		{
			nums[j + 1] = nums[j];
			j--;
		}
		nums[++j] = curr;
	}

	return  "";

}




void f1()
{

		cout << "1";
		
	

}

const int consttest()
{
	int  a = 1;
	a = 4;
	return  a;
}
#include<functional>






#include<sstream>
#include<fstream>

using ptrs= shared_ptr<int >;

void test_para(ptrs s1)
{
	cout << __func__ << endl;

	
	cout << s1.use_count() << endl;
	ptrs curr;
	curr.swap(s1);
	cout << s1.use_count() << endl;
}


void test_para(ptrs * s1)
{
	cout << __func__ << endl;
	cout<<s1->use_count()<<endl;
	ptrs curr;
	curr.swap(*s1);
	cout << s1->use_count() << endl;
	cout << curr.use_count() << endl;  //访问智能指针的成员函数用. 访问智能指针指向对象的成员函数用->

}

// vector<int>   vec // i数由 j最大的 纯奇数累加的值







#define _ENABLE_ATOMIC_ALIGNMENT_FIX
#include <atomic>
#include <thread>

#include "ThreadPool.h"




void callFun(string str)
{
	cout << str << endl;
}

void pool()
{
	ThreadPool pool(10);
	for (int i = 0; i < 5; i++)
	{
		string strs = "123";
		pool.enqueue([&](string& str) {callFun(str); }, strs);
		printf("function name :%s\n", __func__);
	}
}
#include <thread>
#include <chrono>


class mypolls
{

public:
	vector< std::thread > workers;

	mypolls(int k)
	{
		for (size_t i = 0; i < k; ++i)
		{
			workers.emplace_back([this]
				{
					for (;;)
					{
						std::this_thread::sleep_for(std::chrono::seconds(3));
						cout << 3 << endl;


					}
				}
			);
		}
	}

};



struct Good : std::enable_shared_from_this<Good> // 注意：继承
{
public:
	std::shared_ptr<Good> getptr() {
		return shared_from_this();
	}
	void test()
	{
		ptr = getptr();
		cout << ptr.use_count() << endl;
		auto raw_ptr = ptr.get();
		ptr.reset();
		cout << ptr.use_count() << endl;
		cout << raw_ptr->cs << endl;

	}
	int cs = 5;
	shared_ptr<Good> ptr;
	~Good() { std::cout << "Good::~Good() called" << std::endl; }
};

/*  为什么这个不行

class Good : std::enable_shared_from_this<Good> // 注意：继承
{
public:

	std::shared_ptr<Good> getptr() {
		return shared_from_this();
	}
	void test()
	{
		ptr = getptr();
		cout << ptr.use_count() << endl;
		auto raw_ptr = ptr.get();
		ptr.reset();
		cout << ptr.use_count() << endl;
		cout << ptr->cs << endl;

	}
	int cs = 5;
	shared_ptr<Good> ptr;
	~Good() { std::cout << "Good::~Good() called" << std::endl; }
};

*/







bool  CaculateWeekDay2(int y, int m, int d)
{
	if (m == 1 || m == 2) {
		m += 12;
		y--;
	}
	int currWeek = (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400) % 7 + 1;
	int dd = currWeek > 5 ? d-(currWeek - 5) : d-currWeek-2; //找到上一个星期五

	int count = 0;
	while (dd > 0)  //找到有几个周日
	{
		count++;
		dd = dd - 7;
	}
	if (currWeek == 5)
	{
		if (count <= 2)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	else
	{
		if (count == 3)
		{
			return true;
		}
		else
		{
			return false;
		}

	}

}

bool  CaculateWeekDay(int y, int m, int d)
{
	 
	stringstream ss(",m,m,m,xm,dg");
	string str;
	vector<string> vec;
	while (getline(ss,str,','))
	{
		vec.push_back(str);
	}

	if (m == 1 || m == 2) {
		m += 12;
		y--;
	}

	int currWeek = (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400) % 7 + 1;;
	//使用基姆拉尔森计算公式
	int count = 0;
	while (d>0)
	{

		int iWeek = (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400) % 7 + 1;
		d--;
		if (iWeek == 5)
		{
			count++;
		}
	}

	if (count > 3)
	{
		return true;
	}

	else if (count==3)
	{
		if (currWeek == 5)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	else {


		return false;
	}
	
	

}


int josephus(int n, int m)
{
	int i;
	int sum = 0;
	for (i = 2; i <= n; i++)  ///这里的2表示   至少从有两个人开始 
	{
		sum = (sum + m) % i;
	}
	return sum;
}


int josephusR(int n, int k) {
	if (n == 1) return 0;
	else return (josephusR(n - 1, k) + k) % n;
}



#include <regex>

#include "temp.cpp"


template<class T>
void funt()
{
//	T po = new int(8);
	T *poo = (T*)malloc(sizeof(T));
	*poo = 9;
	cout << *poo << endl;
	poo->~T();
	cout << *poo << endl;

}









class A
{
public:
	A()
	{
		cout << "A's constructor" << endl;
	}


	~A()
	{
		cout << "A's destructor" << endl;
	}

	void show()
	{
		cout << "num:" << num << endl;
	}

private:
	int num=3;
};





int main()
{
	cout << sizeof(int);
	int  mem[100];
	mem[0] = 1;
	mem[1] = 1;
	mem[2] = 1;
	mem[3] = 1;
	cout << (void*)mem << endl;  //输出的是首地址
	int * pv = new (mem)int; 
	cout << pv << endl;//输出的是首地址
	getchar();

	while (1);

	
	funt<int>();
	int po = 8;
	int *poo = &po;
//	(*poo).~int();
	myfunc<int> sdxdewe(2);
	sdxdewe.test(6);
	string arrs[5] = {};
	//string (*arrx)[5] =(string*[5])malloc(18);//string *(arr[5]) 不行
	
	 char **pqq = new char *[10];
	pqq[0] =const_cast<char*> ("1222");
	pqq[1] = const_cast<char*> ("1222");
	pqq[2] = const_cast<char*> ("1222");
	
	string strsxxxdad = "123";
	string sddwewe = strsxxxdad.substr(0, 2);
	bool bo1=CaculateWeekDay2(2021,4,15);
	bo1 = CaculateWeekDay2(2021, 4, 17);
	bo1 = CaculateWeekDay2(2021, 4, 30);
	bo1 =CaculateWeekDay2(2021, 5, 2);

	shared_ptr<Good> psss(new Good) ;
	
	psss->test();



	
	//mypolls mypollss(5);

	vector< std::thread > workers;
	for (size_t i = 0; i < 5; ++i)
	{
		workers.emplace_back([=]
		{
			for (;;)
			{
				std::this_thread::sleep_for(std::chrono::seconds(3));
				cout <<i << endl;

				
			}
		}
		);
	}


	while (true)
	{
		std::this_thread::sleep_for(std::chrono::seconds(1));
	}
	pool();
	printf("function name :%s\n",__func__);

	vector<vector<int>> vec(20, vector<int>(20, 0));
	vector<vector<int>> vecset;
	vector<int > currpath;
 	set<int> splitrlt;



	ptrs curr = make_shared<int>(3);
	ptrs curr2(curr);
	test_para(curr2);
	cout << curr2.use_count() << endl;
	test_para(&curr2);
	cout << curr2.use_count() << endl;

	cout << __func__ << endl;
	int b = 1 | 3 ;
	stringstream ss;
	string my1 = "13";
	ss << my1;
	int my2;
	ss >> my2;

	string strsplit;
	stringstream ss2(" s x s d");
	while (true)
	{
		string s1;
		
		ss2 >> s1;
		strsplit = strsplit + s1;
	}
	vector<int> MapChess(5, 0);

	int res = 0;
	while (true)
	{
		res++;
		int previous=0;
		for (int i = 0; i < 5; i++)
		{
			int temp = MapChess[i];  
			MapChess[i] = MapChess[i] + previous + 1;   //注意这句 假设新的MapChess[i]为map[i][j] , 则previous为map[i][j-1]  旧的MapChess[i]为map[i-1][j-1]
			previous = temp;
			if (MapChess[i] >= 6)
				return res;
		

		}





	}



	int as = 1;
	shared_ptr<int> p1(&as);
	cout << p1.use_count() << endl;

	shared_ptr<int> p2(&as);
	cout << p2.use_count() << endl;

	shared_ptr<int> p3=p1;

	cout << p3.use_count() << endl;

	
	vector<int > insert({ 1,2,3 });
	solves(insert);
	function<void() >  f = test2;
	shared_ptr <int> p;
	(*p) = 2;
	shared_ptr <int> q(p);

	int i = 1;
	flip(g, i, 42);
	rparatest(3);
	rref a = fun1();
	return  0;
}

/*int main()

{
	rref &&a = fun1();
	int l3 = sqrt(27);
	vector<int > insert({1,2,3});

	solve(insert);
	char a1[] = "ababababca";
	char a2[] = "abababca";

	int cs=KMP(a1,a2);
	stringstream ss("12#8#22");
	string mytemp;
	ss >> mytemp;

	Codec des;
	//TreeNode *head = des.deserialize("1_2_3_#_#_4_5_#_#_#_#");
	TreeNode *head=des.deserialize("1 # 2 3 # 4 # # 5 # #");

	string str= des.serialize(head);

//	vector<vector<int>> mat({ { 1,2,3,4 }, { 5,6,7,8 }, { 9,10,11,12 }, { 13,14,15,16 }, { 17,18,19,20 }
//		});
	ListNode p1(0);
//	map<ListNode, ListNode> ssmap;
//	ssmap.insert({ p1, p1});

	minDistance("ros","coc");
	const char *p = "sddsdsa";
	char csdf = *p++;
	char sfsafd = *p;

	vector<int> vstr({2,3,4,5,6,7,8});
	ListNode *pq=ListNodeConstructor(vstr);
	reorderList(pq);
	string str1("horse");
		string str2("ros");

	smallInt si,s2;
	si = 4;
	si = s2;
	int cxd = si + 2;
	vector<int> permu{5,5,5,6,6,6,6,6,6};
	MoreThanHalfNum_Solution(permu);
	vector<string> topk({ "a", "b", "a", "c", "d", "d","d","f" });
	topKstrings(topk,3);
	int c=minNumberdisappered(permu);

	LIS(permu);


	sstream ss;
	sstream out;
	vector<vector<int>> ms;
	for(int i=0;i<5;i++)
		for (int j = 0; j < 5; j++)
		{
			if (ms.size() < i + 1)
			{
				ms.push_back({});
			}
			ms[i].push_back(j);
		}
	matrixs(ms);
	char sv = 's';
	sv = 'a' == 'a' ? 'c' : 'd';

	string s = "(([{}]))";
	bool sxdv=isValid(s);
	while (s.length()>0)
	{
		int i = s.length() / 2;
		string ss = s.substr(i-1,2);
		if (ss!="{}"  && ss != "()"&& ss != "[]")
		{
			return false;
		}
		s = s.replace(s.begin()+i-1, s.begin() + i+1,"");
	}
	return true;

	return s.length() == 0;




	//std::array<int, 5> myarray = { 2, 16, 77, 34, 50 };
	int  arr[20] = { 1,2,3,4,5,8 };
	int  arr1[3]= { 9 };

	merge(arr,6, arr1,1);

	vector<int> vsg;
	vsg.push_back(3);

	vsg.push_back(2);
	vsg.push_back(4);
	vsg.push_back(4);
	vsg.push_back(6);
	vsg.push_back(7);
	vsg.push_back(8);



	maxLength(vsg);
	twoSum(vsg,6);

	int rlt = 0;


	//readFile("D:/mydata/LmtFromTDX-all.csv", 1, myfun);

	int k = 5;
	vector <int> input;

	for (int i = 0; i < 20; i++)
	{
		input.push_back(i);
	}
	make_heap(input.begin(), input.end(), [](int&a, int &b) {return a < b; });
	//	make_heap(input.begin(), input.end());
		//cout << input.front() << endl;
	pop_heap(input.begin(), input.end(), [](int&a, int &b) {return a < b; });
	input.pop_back();

	cout << input.front() << endl;

	input.push_back(30);
	push_heap(input.begin(), input.end());
	cout << input.front() << endl;




	unordered_map<int, vector<pair<int, int> >::iterator> cathe2;
	vector < pair<int, int>> vec;

	for (int i = 0; i < 10; i++)
	{

		vec.push_back({ i,i });
	}

	auto itr3 = vec.begin();
	while (itr3 != vec.end())
	{
		cathe2[(*itr3).first] = itr3;
		itr3++;
	}



	auto itr6 = cathe2.find(6);
	vec.erase((*itr6).second);
	cathe2.erase(5);
	auto itrx = cathe2.begin();
	while (itrx != cathe2.end())
	{
		cout << (*(*itrx).second).second << endl;
		itrx++;
	}






	list<pair<int, int> > listtest;
	unordered_map<int, list<pair<int, int> >::iterator> cathe;







	for (int i = 0; i < 10; i++)
	{

		listtest.push_back({ i,i });
	}

	auto itr = listtest.begin();
	while (itr != listtest.end())
	{
		cathe[(*itr).first] = itr;
		itr++;
	}

	auto itr5 = cathe.find(5);
	listtest.erase((*itr5).second);
	cathe.erase(5);
	auto itr2 = cathe.begin();
	while (itr2 != cathe.end())
	{
		cout << (*(*itr2).second).second << endl;
		itr2++;
	}


	int num = 0;
	while (cin >> num)
	{
		if (num <= 1 || num >= 100)
			cout << "ERROR" << endl;
		vector<int > vec(100, 0);
		for (int i = 0; i < 100; i++)
		{
			vec[i] = i + 1;
		}
		calc(vec, num, 0);
		vector<int > vec2;
		for (auto ele : vec)
		{
			if (ele == -1)
				continue;
			vec2.push_back(ele);
		}

		for (int k = 0; k < vec2.size(); k++)
		{
			if (k == vec2.size() - 1)
			{
				cout << vec2[k] << endl;
			}
			else
			{
				cout << vec2[k] << ",";
			}
		}

	}




}
*/



/*
#include <iostream>
#include <vector>
#include <string>
#include <regex>

using namespace std;


vector<string> split(string input, string pattern)
{
	regex re(pattern);
	sregex_token_iterator   first(input.begin(), input.end(), re, -1), last;
	return { first,last };
}

int main()
{
	string str;
	vector<vector<char>> vec;
	vector<char> vec1;
	vector<string> vec2;


	//while (cin>>str)
	//{
	//	vec2.push_back(str);
	//}

	while(getline(cin,str))
	{



		regex re(" ");
		sregex_token_iterator   first(str.begin(), str.end(), re, -1), last;
		while (first!=last)
		{
			vec2.push_back(*first);
			first++;
		}

		for (int i = 0; i < str.size() - 1; i=i+4)
		{

			if (str[i+2] == 'N')
			{
				if (vec1.size() > 0)
				{
					vec.push_back(vec1);
				}
				vec1.clear();
				vec1.push_back(str[i]);
			}
			else
			{
				vec1.push_back(str[i]);
			}
		}
		vec.push_back(vec1);

		for (int i = 0; i < vec.size(); i++)
		{
			for (int j = 0; j < vec[i].size(); j++)
			{
				if (j == vec[i].size() - 1)
				{
					cout << vec[i][j] << endl;
				}
				else {
					cout << vec[i][j] << " ";
				}
			}

		}

	}



	return 0;

}

*/





/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

















 /**
  * Definition for binary tree
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */



























